package com.practice.zuocy.base.class07;

/**
 * （1）二叉树的节点结构：
 * public static class Node {
 * 		public int value;
 * 		public Node left;
 * 		public Node right;
 *
 * 		public Node(int v) {
 * 			value = v;
 *      }
 *  }
 * （2）递归方法实现：二叉树的先序、中序、后序遍历
 */
public class Code01_RecursiveTraversalBT {

	/**
	 * 二叉树的节点结构
	 */
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int v) {
			value = v;
		}
	}

	/*
	 * 二叉树的先序、中序、后序遍历：
	 * （1）先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树
	 * （2）中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树
	 * （3）后序：任何子树的处理顺序都是，先左子树，再右子树，然后头节点
	 */

	/**
	 * 递归基本结构概述：
	 * （1）二叉树递归版本的先、中、后序遍历，其实就是基于一个固定的递归结构，
	 * 然后将二叉树节点的打印语句放在不同的位置的3种情况。
	 * （2）这个固定的递归结构为：根据二叉树节点的特点，遍历完当前节点自己的value后，递归的去遍历其左子树和右子树。
	 * （3）先序遍历二叉树节点打印语句的顺序为，将打印语句放在进递归函数之前，也就是直接打印当前节点。
	 * （4）中序遍历二叉树节点打印语句的顺序为，将打印语句放在左子树递归函数返回之后，进入右子树递归函数之前。
	 * （5）后序遍历二叉树节点打印语句的顺序为，将打印语句放在所有递归函数返回之后。
	 *
	 * @param head 当前节点
	 */
	public static void f(Node head) {
		if (head == null) {
			return;
		}
		// 1
		f(head.left);
		// 2
		f(head.right);
		// 3
	}

	// 递归：先序打印所有节点
	public static void pre(Node head) {
		if (head == null) {
			return;
		}
		System.out.println(head.value);
		pre(head.left);
		pre(head.right);
	}

	// 递归：中序
	public static void in(Node head) {
		if (head == null) {
			return;
		}
		in(head.left);
		System.out.println(head.value);
		in(head.right);
	}

	// 递归：后序
	public static void pos(Node head) {
		if (head == null) {
			return;
		}
		pos(head.left);
		pos(head.right);
		System.out.println(head.value);
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		pre(head);
		System.out.println("========");
		in(head);
		System.out.println("========");
		pos(head);
		System.out.println("========");

	}

}
